The present invention generally relates to character recognition apparatus, and more particularly to a character recognition apparatus which employs an n degree peripheral pattern to compress feature data extracted from a character.
Compression of feature data extracted from a character using the n degree peripheral pattern has been proposed in the past. According to this proposed compression using the n degree peripheral pattern, a direction code is added to contour picture elements of a character pattern. The direction code indicates the direction in which the picture elements constituting the character pattern extend. FIG. 1 shows an example of the direction code in relation to the dot pattern. In FIG. 1, a black dot indicates a picture element of the character pattern, and a white dot indicates a contour picture element of the character pattern. When assigning the direction code to the picture elements included in a frame F shown in FIG. 2 which contains the character pattern, a matching is made to determine the direction code for each picture element.
In FIG. 2, only a portion of the picture elements are shown for convenience' sake, and the direction code is indicated at the position of the picture element. No direction code is assigned to the picture elements of the character pattern, but it is also possible to assign a direction code to such picture elements by modifying the direction codes shown in FIG. 1. The frame F containing the character pattern is scanned from each side of the frame to a confronting side of the frame as indicated by arrows in FIG. 2, so as to detect the direction code which appears next to the white (background). For example, the direction code detected first along the scanning line is classified as a first direction code and the direction code detected second is classified as a second direction code. The frame is divided into a plurality of regions, and a histogram of the direction codes is obtained to a certain degree of the direction code with respect to each of the regions. A vector having the histogram values as components thereof is used as a feature vector describing the feature of the character pattern.
In other words, when the frame is divided into four regions, for example, distances to the contour picture elements along the scanning direction are calculated for each region, so as to describe the character pattern in terms of such distances. The calculated distances are referred to as a peripheral pattern describing the feature of the character pattern. Hence, the distance to the first contour picture element along the scanning direction in each region constitutes the first peripheral pattern, and the distance to the second detected contour picture element along the scanning direction in each region constitutes a second peripheral pattern.
The assigning of the direction code (or directionality code) to the picture elements and the use of the n degree peripheral pattern (or multilayer directionality code histogram method) are further disclosed in the U.S. Pat. application Ser. No. 069,303 filed July 2, 1987, now U.S. Pat. No. 4,903,313, the disclosure of which is hereby incorporated by reference.
When making a character recognition, such a feature vector is extracted from an input character pattern, and an operation is carried out to calculate a distance between the feature vector of the input character pattern and feature vectors of standard patterns registered in a dictionary. When the distance becomes a minimum with respect to the feature vector of a certain standard pattern, the input character pattern is recognized as a character having the certain standard pattern.
The use of the n degree peripheral pattern is advantageous in that the character recognition can be made with a high accuracy with respect to a character having a large deformation such as a hand-written character. However, there is a problem in that the degree of the feature vector becomes large. For example, when eight kinds of codes are added as the direction code, the frame of the character pattern is made up of regions of four by four and the direction code is extracted to the second peripheral pattern, the degree of the feature vector becomes 256 (=4.times.4.times.2.times.8).
When the degree of the feature vector is large, there are problems in that the capacity of the dictionary becomes large and a matching time becomes long due to the increased operation to calculate the distance between the feature vector of the input character pattern and the feature vectors of standard patterns registered in the dictionary. A data compression of the feature vector is effective in eliminating these problems.
There basically are two data compression methods. A first data compression method is based on an orthogonal transform such as the Fourier transform using the frequency characteristic of the subject data, the main component analysis using statistical characteristic, or the Karhunen-Loeve transform. The application of such methods to the character pattern is known from "HANDWRITING, TYPE OCR" by Sakai et al, Toshiba Review, Vol.38, No.13, 1983, for example. On the other hand, the application to the feature vector is known from "HAND-WRITTEN KANJI AND HIRAGANA RECOGNITION USING WEIGHT DIRECTION EXPONENTIAL HISTOGRAM AND PSEUDO BAYES DISCRIMINATION" by Harada et al, Shingakugiho, PRL83-68, 1983. However, processes based on such methods are generally complex and difficult to carry out at a high speed. For this reason, these methods are not suited for the purpose of reducing the matching time.
A second data compression method is based on the delta modulation or differential pulse code modulation (DPCM) which are used for data having a strong correlation such as time-sequential data, or the run length code, MH code, MR code or the like which are used for image data compression. However, when an attempt is made to improve the data compression rate by using such methods, there is a problem in that the distortion in the reproduced data becomes large. Therefore, these methods are not suited for compression of the feature vector when using the n degree peripheral pattern.
Recently, there is attention on the vector quantization due to the rate-distortion theory which clarifies the problems of the data compression rate and the distortion in the reproduced data. The application to audio and image data compression is disclosed in "VECTOR QUANTIZATION" by Tasaki et al, Shingakkaishi, Vol.67, No.5, 1984 and "COMPRESSION OF PRINTING IMAGE USING APPLIED VECTOR QUANTIZATION" by Kaizu et al, Shingakugiho IE86-94, 1986, for example.
If the quantization unit (group) can be appropriately determined, a high data compression rate can be anticipated. However, although the quantization unit (group) is evident for the time-sequential data such as the audio data, the appropriate quantization unit and concrete conditions are not yet established for the feature vectors used in the character recognition such as the feature vector used in the n degree peripheral pattern. For this reason, the quantizing error is large in the conventional case.